package com.review.dp;

import java.util.Arrays;

public class LC_494 {
    public static int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(S) > sum || (sum + S) % 2 != 0) {
            return 0;
        }
        int target = (sum + S) / 2;

        int[] dp = new int[target + 1];
        int[] count = new int[target + 1];
        Arrays.fill(count, 1);

        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                if (dp[j] < dp[j - nums[i]] + nums[i]) {
                    // 选择当前物品更合适
                    count[j] = count[j - nums[i]];
                } else if (dp[j] == dp[j - nums[i]] + nums[i]) {
                    // 选不择选择当前物品都合适
                    count[j] += count[j - nums[i]];
                } else {
                    // 不选择当前物品更合适
                }
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return count[target];
    }

    public static void main(String[] args) {
        System.out.println(findTargetSumWays(new int[]{100}, -200));
    }
}
